package main

import "strings"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param A string字符串
 * @param n int整型
 * @return int整型
 */
func getLongestPalindromeManacher(A string, n int) int {
	// write code here
	if n <= 1 {
		return n
	}
	ss := "$#"
	for i := 0; i < n; i++ {
		ss = ss + A[i:i+1] + "#"
	}
	ss = ss + "`"
	l := len(ss)
	p := make([]int, l)
	max_str := ""
	mx := 0
	center := 0
	for i := 1; i < l-1; i++ {
		if mx > i {
			j := 2*center - i
			if p[j] < mx-i {
				p[i] = p[j]
			} else {
				p[i] = mx - i
			}
		}
		for pj := p[i] + 1; ss[i-pj] == ss[i+pj]; pj++ {
			p[i]++
		}
		if p[i] > mx {
			center = i
			mx = i + p[i]
		}
		if 2*p[i]+1 > len(max_str) {
			max_str = ss[i-p[i] : i+p[i]+1]
		}
	}
	return len(strings.ReplaceAll(max_str, "#", ""))
}

func main() {
	getLongestPalindromeManacher("abc1234321ab", 12)
}
